#include <stdio.h>
#include <stdlib.h>

// 多项式结构体
typedef struct Polynomial {
    int degree;
    int *coefficients; // 系数数组，coefficients[0]是常数项
} Polynomial;

// 创建多项式
Polynomial* create_polynomial(int degree) {
    Polynomial *poly = (Polynomial*)malloc(sizeof(Polynomial));
    poly->degree = degree;
    poly->coefficients = (int*)calloc(degree + 1, sizeof(int));
    return poly;
}

// 释放多项式
void free_polynomial(Polynomial *poly) {
    free(poly->coefficients);
    free(poly);
}

// 多项式乘法（假设已实现O(logi)算法）
Polynomial* multiply_polynomials(Polynomial *p1, Polynomial *p2) {
    int new_degree = p1->degree + p2->degree;
    Polynomial *result = create_polynomial(new_degree);
    
    // 这里简化为O(n^2)的朴素乘法，实际应使用题目中提到的O(logi)算法
    for (int i = 0; i <= p1->degree; i++) {
        for (int j = 0; j <= p2->degree; j++) {
            result->coefficients[i + j] += p1->coefficients[i] * p2->coefficients[j];
        }
    }
    
    return result;
}

// 构造线性因子 (x - n)
Polynomial* create_linear_factor(int n) {
    Polynomial *factor = create_polynomial(1);
    factor->coefficients[1] = 1;  // x
    factor->coefficients[0] = -n; // -n
    return factor;
}

// 分治法构造多项式
Polynomial* build_polynomial(int *roots, int left, int right) {
    if (left == right) {
        return create_linear_factor(roots[left]);
    }
    
    int mid = left + (right - left) / 2;
    Polynomial *left_poly = build_polynomial(roots, left, mid);
    Polynomial *right_poly = build_polynomial(roots, mid + 1, right);
    Polynomial *product = multiply_polynomials(left_poly, right_poly);
    
    free_polynomial(left_poly);
    free_polynomial(right_poly);
    
    return product;
}

// 构造满足条件的多项式
Polynomial* construct_polynomial(int *roots, int d) {
    Polynomial *result = build_polynomial(roots, 0, d - 1);
    
    // 确保最高次项系数为1
    if (result->coefficients[result->degree] != 1) {
        int leading_coeff = result->coefficients[result->degree];
        for (int i = 0; i <= result->degree; i++) {
            result->coefficients[i] /= leading_coeff;
        }
    }
    
    return result;
}

// 打印多项式
void print_polynomial(Polynomial *poly) {
    printf("P(x) = ");
    for (int i = poly->degree; i >= 0; i--) {
        if (poly->coefficients[i] == 0) continue;
        
        if (i < poly->degree && poly->coefficients[i] > 0) {
            printf(" + ");
        } else if (poly->coefficients[i] < 0) {
            printf(" - ");
        }
        
        int abs_coeff = abs(poly->coefficients[i]);
        if (abs_coeff != 1 || i == 0) {
            printf("%d", abs_coeff);
        }
        
        if (i > 0) {
            printf("x");
            if (i > 1) {
                printf("^%d", i);
            }
        }
    }
    printf("\n");
}

// 测试函数
int main() {
    int d = 3;
    int roots[] = {1, 2, 3}; // 多项式有零点1, 2, 3
    
    Polynomial *poly = construct_polynomial(roots, d);
    
    printf("Constructed polynomial with roots at 1, 2, 3:\n");
    print_polynomial(poly);
    
    free_polynomial(poly);
    
    return 0;
}